﻿
namespace Leetcode.N2218;

public class Solution
{
    public int MaxValueOfCoins(IList<IList<int>> piles, int k)
    {

        var sums = new int[piles.Count][];
        for (int i = 0; i < piles.Count; i++)
        {
            sums[i] = new int[piles[i].Count];
            sums[i][0] = piles[i][0];
            for (int j = 1; j < piles[i].Count; j++)
            {
                sums[i][j] = piles[i][j] + sums[i][j - 1];
            }
        }

        var vals = new int[piles.Count][];

        for (int i = 0; i < sums.Length; i++)
        {
            vals[i] = new int[k + 1];

            for (int j = 1; j <= k; j++)
            {
                if (i == 0)
                {
                    vals[i][j] = (j <= sums[i].Length) ? sums[i][j - 1] : sums[i][sums[i].Length - 1];
                    continue;
                }

                vals[i][j] = vals[i - 1][j];
                for (int x = 0; x < sums[i].Length && x < j; x++)
                {
                    vals[i][j] = Math.Max(vals[i][j], sums[i][x] + vals[i - 1][j - (x + 1)]);
                }
            }
        }

        return vals[vals.Length - 1][k];

    }
}
